package com.leetcode.algorithm.y22.m07.w4;

/**
 * 560. 和为 K 的子数组
 * 
 * https://leetcode.cn/problems/subarray-sum-equals-k/
 * 
 * @author jie.deng
 *
 */
class Question0560Solution02 {

	public int subarraySum(int[] nums, int k) {
		int len = nums.length;
		int cnt = 0;

		// dp[i][j] 表示 num[i...j]之和
		// dp[0][0]
		// dp[0][1],dp[1][1]
		// dp[0][2],dp[1][2],dp[2][2]
		// dp[0][3],dp[1][3],dp[2][3],dp[3][2]
		int[] dp = new int[len];
		for (int i = 0; i < len; i++) {
			dp[i] = nums[i];
			if (dp[i] == k) {
				cnt++;
			}
			int diff = k - dp[i];
			for (int j = 0; j < i; j++) {
				if (diff == dp[j]) {
					cnt++;
				}
				dp[j] += nums[i];
			}
		}
		return cnt;
	}

}